A Bayesian network is a model that represents variables and conditional interdependencies between variables. In a Bayesian network variables are represented as nodes, and nodes may be connected to one another by one or more links. A link indicates a relationship between two nodes. Nodes typically have corresponding conditional probability tables that are used to determine the probability of a state of a node given the state of other nodes to which the node is connected. One common use of a Bayesian network is to diagnose problems, such as diseases.
In operation, a Bayesian network typically grows over time. New nodes may be added, and/or new links between nodes may be established as new relationships between nodes are discovered. Unfortunately, as a Bayesian network grows, the processing associated with determining probabilities increases exponentially. For example, if a child node has m parent nodes, then the probability function for the child node is represented by a table of 2m entries, one entry for each of the 2m possible combinations of its parent nodes being true or false. This exponential increase results in increased processing time associated with inference operations performed by the Bayesian network during operation. The increased processing time may be unacceptable under normal operating conditions.
Accordingly, there is a need for a mechanism for reducing the number of links between nodes in a Bayesian network without negatively impacting inferential accuracy of the network.